package arithmetic.dynamicprogramming;

/* A DynamicProgramming solution for Climbing Stairs' problem Returns the
    distinct ways can you climb to the staircase by either climbing 1 or 2 steps.

    Link : https://medium.com/analytics-vidhya/leetcode-q70-climbing-stairs-easy-444a4aae54e8
*/
public class ClimbingStairs {

    public static void main(String[] args) {
        System.out.println(numberOfWays(6));
    }

    /**
     * 递推公式：f(n) = f(n-1) + f(n-2)
     * 递归实现时间空间复杂度太高，因此可以用变量求和
     * @param n
     * @return
     */
    public static int numberOfWays(int n) {
        if (n <= 2) {
            return n;
        }
        // 初始条件
        int f1 = 1;
        int f2 = 2;
        int fi = f1 + f2;

        for (int i = 3; i <= n; i++) {
            fi = f1 + f2;
            f1 = f2;
            f2 = fi;
        }

        return fi;
    }
}
//important